/**
 * vim: filetype=c:fenc=utf-8:ts=4:et:sw=4:sts=4
 */
#include <sys/types.h>
#include <string.h>
#include <stdint.h>
#include <unistd.h>
#include <syscall.h>
#include <stdio.h>

// 实验5：内存分配器
size_t heap_size = (size_t)(1024 * 1024 * 1); // 1000MB
// 互斥锁
int mutex;

struct chunk
{
  char signature[4];  /* "OSEX" */
  struct chunk *next; /* ptr. to next chunk */
  int state;          /* 0 - free, 1 - used */
#define FREE 0
#define USED 1

  int size; /* size of this chunk */
};

static struct chunk *chunk_head;

void *g_heap;
void *tlsf_create_with_pool(uint8_t *heap_base, size_t heap_size)
{
  chunk_head = (struct chunk *)heap_base;
  strncpy(chunk_head->signature, "OSEX", 4);
  chunk_head->next = NULL;
  chunk_head->state = FREE;
  chunk_head->size = heap_size;

  mutex = sem_create(1);

  return NULL;
}

// 实验5：内存分配器
void *malloc(size_t size)
{
  if (size == 0)
    return NULL;
  // 临界区
  sem_wait(mutex);

  // current为分配出来的块
  struct chunk *current = chunk_head;

  //首次适应算法
  while (current != NULL)
  {
    // 检查当前块是否空闲且大小足够
    if (current->state == FREE && current->size >= size + sizeof(struct chunk))
    {
      // 如果当前块大小比所需大小大很多，我们可以分割该块
      if (current->size >= size + 2 * sizeof(struct chunk))
      {
        // 分割块                                  //char*每次++ 为1bytes//整个内存池管理块大小  //实际使用块大小
        struct chunk *new_chunk = (struct chunk *)((char *)current + sizeof(struct chunk) + size);
        strncpy(new_chunk->signature, "OSEX", 4);
        new_chunk->next = current->next;
        new_chunk->state = FREE;
        new_chunk->size = current->size - size - sizeof(struct chunk); // 更新新块的size

        current->next = new_chunk;
        current->size = size;
      }



      // 标记当前块为已使用
      current->state = USED;

      sem_signal(mutex);
      // printf("sem_signal(mutex)\n");
      // 返回内存块的起始地址（跳过管理块）
      return (void *)((char *)current + sizeof(struct chunk));
    }

    // 移动到下一个块
    current = current->next;
  }
  sem_signal(mutex);
  // printf("sem_signal(mutex)\n");

  printf("[malloc: no suitable chunk found]\n");
  // 没有找到合适的块，返回 NULL
  return NULL;
}

void free(void *ptr)
{
  if (ptr == NULL)
    return;
  // 临界区
  sem_wait(mutex);
  // 寻找管理块
  struct chunk *achunk = (struct chunk *)(((uint8_t *)ptr) - sizeof(struct chunk));
  // 检查签名
  if (strncmp(achunk->signature, "OSEX", 4) != 0)
  {
    printf("[free: invalid pointer]\n");
    sem_signal(mutex);
    // printf("sem_signal(mutex)\n");
    return;
  }
  // 检查是否已经释放
  if (achunk->state == FREE)
  {
    printf("[free: double free]\n");
    sem_signal(mutex);
    // printf("sem_signal(mutex)\n");
    return;
  }

  // 标记为未使用
  achunk->state = FREE;

  // 合并相邻的空闲块，检查啊春款前后是否为FREE：若为FREE，则合并
  // 若achunk不是最后一个块，检查下一个块是否空闲
  if (achunk->next != NULL)
  {
    // struct chunk *next_chunk = (struct chunk *)((char *)achunk + sizeof(struct chunk) + achunk->size);
    struct chunk *next_chunk = achunk->next;
    // printf("next_chunk = %p,achunk->next =%p\n",next_chunk,achunk->next);

    if (next_chunk->state == FREE)
    {
      // printf("next_chunk->state == FREE\n");

      // 合并size
      achunk->size += sizeof(struct chunk) + next_chunk->size;
      achunk->next = next_chunk->next;
    }
    else // 非空闲
    {
      achunk->next = next_chunk;
    }
  }

  // 若achunk不是第一个块，检查前一个块是否空闲
  if (achunk != chunk_head)
  {
    struct chunk *prev_chunk = chunk_head;
    // 找到前一个块
    while (prev_chunk != NULL && prev_chunk->next != achunk)
    {
      prev_chunk = prev_chunk->next;
    }
    // 如果前一个块存在且是空闲的
    if (prev_chunk != NULL && prev_chunk->state == FREE)
    {
      // 合并size
      prev_chunk->size += sizeof(struct chunk) + achunk->size;
      prev_chunk->next = achunk->next;
    }
    else if (prev_chunk != NULL && prev_chunk->state != FREE) // 非空闲
    {
      prev_chunk->next = achunk;
    }
  }

  sem_signal(mutex);
  // printf("sem_signal(mutex)\n");

}

void *calloc(size_t num, size_t size)
{
  if (num == 0 || size == 0)
    return NULL;
  size_t total_size = num * size;
  void *ptr = malloc(total_size);
  if (ptr == NULL)
    return NULL;
  
  
  // 将分配的内存初始化为0
  memset(ptr, 0, total_size);
  return ptr;
}

void *realloc(void *oldptr, size_t size)
{
  if (oldptr == NULL)
    return malloc(size);
  if (size == 0)
  {
    free(oldptr);
    return NULL;
  }
  // 获取当前块的管理块
  struct chunk *achunk = (struct chunk *)(((uint8_t *)oldptr) - sizeof(struct chunk));
  // 检查签名
  if (strncmp(achunk->signature, "OSEX", 4) != 0)
  {
    printf("[realloc: invalid pointer]\n");
    return NULL;
  }
  // 检查是否已经释放
  if (achunk->state == FREE)
  {
    printf("[realloc: double free]\n");
    return NULL;
  }
  // 检查是否可以在原地扩展
  if (achunk->size >= size)
  {
    // 如果可以扩展，直接返回原指针
    return oldptr;
  }
  // 如果不能扩展，分配新的内存块
  void *newptr = malloc(size);
  if (newptr == NULL)
  {
    return NULL;
  }
  // 复制旧数据到新内存块
  memcpy(newptr, oldptr, achunk->size);
  // 释放旧内存块
  free(oldptr);
  // 返回新内存块的指针
  return newptr;
}

/*************D O  N O T  T O U C H  A N Y T H I N G  B E L O W*************/
static void tsk_malloc(void *pv)
{
  int i, c = (int)pv;
  char **a = malloc(c * sizeof(char *));
  for (i = 0; i < c; i++)
  {
    a[i] = malloc(i + 1);
    a[i][i] = 17;
  }
  for (i = 0; i < c; i++)
  {
    free(a[i]);
  }
  free(a);

  task_exit(0);
}

#define MESSAGE(foo) printf("%s, line %d: %s", __FILE__, __LINE__, foo)
void test_allocator()
{
  char *p, *q, *t;

  MESSAGE("[1] Test malloc/free for unusual situations\r\n");

  MESSAGE("  [1.1]  Allocate small block ... ");
  p = malloc(17);
  if (p == NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  p[0] = p[16] = 17;
  printf("PASSED\r\n");

  MESSAGE("  [1.2]  Allocate big block ... ");
  q = malloc(4711);
  if (q == NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  q[4710] = 47;
  printf("PASSED\r\n");

  MESSAGE("  [1.3]  Free big block ... ");
  free(q);
  printf("PASSED\r\n");

  MESSAGE("  [1.4]  Free small block ... ");
  free(p);
  printf("PASSED\r\n");

  MESSAGE("  [1.5]  Allocate huge block ... ");
  q = malloc(32 * 1024 * 1024 - sizeof(struct chunk));
  if (q == NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  q[32 * 1024 * 1024 - sizeof(struct chunk) - 1] = 17;
  free(q);
  printf("PASSED\r\n");

  MESSAGE("  [1.6]  Allocate zero bytes ... ");
  if ((p = malloc(0)) != NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  printf("PASSED\r\n");

  MESSAGE("  [1.7]  Free NULL ... ");
  free(p);
  printf("PASSED\r\n");

  MESSAGE("  [1.8]  Free non-allocated-via-malloc block ... ");
  int arr[5] = {0x55aa4711, 0x5a5a1147, 0xa5a51471, 0xaa551741, 0x5aa54171};
  free(&arr[4]);
  if (arr[0] == 0x55aa4711 &&
      arr[1] == 0x5a5a1147 &&
      arr[2] == 0xa5a51471 &&
      arr[3] == 0xaa551741 &&
      arr[4] == 0x5aa54171)
  {
    printf("PASSED\r\n");
  }
  else
  {
    printf("FAILED\r\n");
    return;
  }

  MESSAGE("  [1.9]  Various allocation pattern ... ");
  int i;
  size_t pagesize = sysconf(_SC_PAGESIZE);
  for (i = 0; i < 7411; i++)
  {
    p = malloc(pagesize);
    p[pagesize - 1] = 17;
    q = malloc(pagesize * 2 + 1);
    q[pagesize * 2] = 17;
    t = malloc(1);
    t[0] = 17;
    free(p);
    free(q);
    free(t);
  }

  char **a = malloc(2741 * sizeof(char *));
  for (i = 0; i < 2741; i++)
  {
    a[i] = malloc(i + 1);
    a[i][i] = 17;
  }
  for (i = 0; i < 2741; i++)
  {
    free(a[i]);
  }
  free(a);

  if (chunk_head->next != NULL || chunk_head->size != 32 * 1024 * 1024)
  {
    printf("FAILED\r\n");
    return;
  }
  printf("PASSED\r\n");

  MESSAGE("  [1.10] Allocate using calloc ... ");
  int *x = calloc(17, 4);
  for (i = 0; i < 17; i++)
    if (x[i] != 0)
    {
      printf("FAILED\r\n");
      return;
    }
    else
      x[i] = i;
  free(x);
  printf("PASSED\r\n");

  MESSAGE("[2] Test realloc() for unusual situations\r\n");

  MESSAGE("  [2.1]  Allocate 17 bytes by realloc(NULL, 17) ... ");
  p = realloc(NULL, 17);
  if (p == NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  p[0] = p[16] = 17;
  printf("PASSED\r\n");
  MESSAGE("  [2.2]  Increase size by realloc(., 4711) ... ");
  p = realloc(p, 4711);
  if (p == NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  if (p[0] != 17 || p[16] != 17)
  {
    printf("FAILED\r\n");
    return;
  }
  p[4710] = 47;
  printf("PASSED\r\n");

  MESSAGE("  [2.3]  Decrease size by realloc(., 17) ... ");
  p = realloc(p, 17);
  if (p == NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  if (p[0] != 17 || p[16] != 17)
  {
    printf("FAILED\r\n");
    return;
  }
  printf("PASSED\r\n");

  MESSAGE("  [2.4]  Free block by realloc(., 0) ... ");
  p = realloc(p, 0);
  if (p != NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  else
    printf("PASSED\r\n");

  MESSAGE("  [2.5]  Free block by realloc(NULL, 0) ... ");
  p = realloc(realloc(NULL, 0), 0);
  if (p != NULL)
  {
    printf("FAILED\r\n");
    return;
  }
  else
    printf("PASSED\r\n");

  MESSAGE("[3] Test malloc/free for thread-safe ... ");

  int t1, t2;
  char *s1 = malloc(1024 * 1024),
       *s2 = malloc(1024 * 1024);
  t1 = task_create(s1 + 1024 * 1024, tsk_malloc, (void *)5000);
  t2 = task_create(s2 + 1024 * 1024, tsk_malloc, (void *)5000);
  task_wait(t1, NULL);
  task_wait(t2, NULL);
  free(s1);
  free(s2);

  if (chunk_head->next != NULL || chunk_head->size != 32 * 1024 * 1024)
  {
    printf("FAILED\r\n");
    return;
  }
  printf("PASSED\r\n");
}
/*************D O  N O T  T O U C H  A N Y T H I N G  A B O V E*************/


